Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Introduction to Tree Depth First Search Pattern

The Tree Depth-First Search (DFS) traversal is a key technique in binary tree operations. It focuses on exploring one branch of the tree as far as possible before backtracking. This approach is useful for problems requiring tree traversal or handling hierarchical data.

The main types of DFS traversals include:

  • Pre-order Traversal: Visit the root node first, then the left subtree, and finally the right subtree.
  • In-order Traversal: Visit the left subtree first, then the root node, and finally the right subtree.
  • Post-order Traversal: Visit the left and right subtrees first, and then the root node.

These techniques we have already discussed in the introduction chapter.

To solve DFS-based problems, the approach generally involves:

  • Recursive approach: Simple and follows the natural structure of a tree.
  • Iterative approach: Uses a stack to mimic recursion and helps in memory optimization.

DFS is ideal for scenarios where exploring entire paths or working with node relationships is essential.

Let's understand the Tree DFS (Depth-First Search) traversal via the below problem.

Problem Statement

Given the root of a binary tree, explore all possible root-to-leaf paths, compute the sum of values along each path, and return the minimum sum.

A leaf node is a node with no children.

Examples

Example 1:

  • Input: root = [10, 5, 15, null, null, 7, 20]
Image
  • Expected Output: 15
  • Justification: The path with the minimum sum is 10 -> 5. The sum is 10 + 5 = 15.

Example 2:

  • Input: root = [-1, 2, 3, 4, 5, 1]
Image
  • Expected Output: 3
  • Justification: The path with the minimum sum is -1 -> 3 -> 1. The sum is -1 + 3 + 1 = 3.

Example 3:

  • Input: root = [8, 40, 12, null, null, 10, 18, 2]
Image
  • Expected Output: 32
  • Justification: The path with the minimum sum is 8 -> 12 -> 10 -> 2. The sum is 8 + 12 + 10 + 2 = 32.

Solution

The algorithm calculates the minimum root-to-leaf path sum in a binary tree using a recursive approach. Starting at the root, it recursively explores the left and right subtrees, computes the minimum sum for each subtree, and adds the current node's value to the smaller of the two sums.

The base case is when the node is null, in which case the function returns 0. The recursion proceeds until it reaches the leaf nodes, and the minimum of the left and right sums is computed as it go back to the parent node of the particular node in the tree.

Step-by-Step Algorithm

  1. Base Case for Null Nodes:

    • If the current node (root) is null, return Integer.MAX_VALUE. This ensures that we do not consider non-existent paths while calculating the minimum sum.
  2. Base Case for Leaf Nodes:

    • If the current node is a leaf node (i.e., both left and right children are null), return the current node’s value (root.val) as a minimum sum. A leaf node is the endpoint of a valid path.
  3. Recursive Case for Non-leaf Nodes:

    • Step 3.1: Recursively compute the minimum sum for the left subtree by calling the same function on root.left.
    • Step 3.2: Recursively compute the minimum sum for the right subtree by calling the same function on root.right.
  4. Minimum Sum Calculation:

    • After computing the minimum sums for both the left and right subtrees, take the smaller of the two values using min(leftSum, rightSum).
  5. Add Current Node's Value:

    • Add the current node's value to the minimum of the left and right subtree sums.
  6. Return the Result:

    • Return the computed minimum root-to-leaf sum for the current node.

Algorithm Walkthrough

Image

Step 1: Start at the root node (-1)

  • The current node value is -1.
  • We need to calculate the minimum root-to-leaf path sum for both its left subtree (2) and right subtree (3).

Step 2: Traverse the left subtree of node (-1) (node 2)

  • The current node is 2.
  • We now need to calculate the minimum sum for both the left subtree (4) and the right subtree (5) of node 2.

Step 3: Traverse the left child of node 2 (node 4)

  • The current node is 4.
  • 4 is a leaf node (both children are null), so we return its value, which is 4.

Step 4: Traverse the right child of node 2 (node 5)

  • The current node is 5.
  • 5 is a leaf node (both children are null), so we return its value, which is 5.

Step 5: Calculate the minimum sum for node 2

  • Now that we have the sums for both children of node 2:
    • Left subtree (node 4) sum: 4
    • Right subtree (node 5) sum: 5
  • The minimum sum from node 2 to a leaf is:
    2 + min(4, 5) = 2 + 4 = 6.

Step 6: Traverse the right subtree of node (-1) (node 3)

  • The current node is 3.
  • We now need to calculate the minimum sum for its left subtree (1) (node 3 has no right child).

Step 7: Traverse the left child of node 3 (node 1)

  • The current node is 1.
  • 1 is a leaf node (both children are null), so we return its value, which is 1.

Step 8: Calculate the minimum sum for node 3

  • Since node 3 only has a left child:
    • Left subtree (node 1) sum: 1
  • The minimum sum from node 3 to a leaf is:
    3 + 1 = 4.

Step 9: Calculate the minimum sum for the root node (-1)

  • Now that we have the sums for both subtrees of the root node -1:
    • Left subtree (node 2) sum: 6
    • Right subtree (node 3) sum: 4
  • The minimum sum from the root -1 to a leaf is:
    -1 + min(6, 4) = -1 + 4 = 3.

Final Result:

The minimum root-to-leaf path sum for the given tree is 3, following the path -1 -> 3 -> 1.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of this solution is , where N is the number of nodes in the binary tree. This is because the algorithm visits every node exactly once, performing constant-time work at each node (i.e., calculating the minimum of the left and right subtrees).

Space Complexity

The space complexity is determined by the recursion stack.

In the worst case (for example, a completely unbalanced tree), the space complexity can be , as the recursion stack may need to go as deep as the height of the tree, which could be N in the case of a skewed tree.

In the best case (a balanced binary tree), the space complexity is , where the maximum depth of recursion would be the height of the tree, which is log N for a balanced tree.

Now, let's start solving the problem on Tree DFS Pattern.

Solution: Connect All Level Order Siblings
Binary Tree Path Sum (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Algorithm Walkthrough

Step 1: Start at the root node (-1)

Step 2: Traverse the left subtree of node (-1) (node 2)

Step 3: Traverse the left child of node 2 (node 4)

Step 4: Traverse the right child of node 2 (node 5)

Step 5: Calculate the minimum sum for node 2

Step 6: Traverse the right subtree of node (-1) (node 3)

Step 7: Traverse the left child of node 3 (node 1)

Step 8: Calculate the minimum sum for node 3

Step 9: Calculate the minimum sum for the root node (-1)

Final Result:

Code

Complexity Analysis